package com.cat.dataStructure02;

import java.util.Arrays;

/**
 *   @description https://leetcode.cn/problems/xepqZ5/
 *   @author 曲大人的喵
 *   @create 2025/10/31 14:46
 *   @since JDK17
 */

public class Solution85 {
    public int fieldOfGreatestBlessing(int[][] forceField) {
        int n = forceField.length, ans = 0, i = 0, j = 0;
        long[] xs = new long[n << 1], ys = new long[n << 1];
        for (var f : forceField) {
            long x = f[0], y = f[1], r = f[2];
            xs[i++] = (x << 1) - r;
            xs[i++] = (x << 1) + r;
            ys[j++] = (y << 1) - r;
            ys[j++] = (y << 1) + r;
        }
        // 离散化
        int xz = sort(xs), yz = sort(ys);
        // 二维差分
        int[][]diff = new int[xz + 2][yz + 2];
        i = 0;
        for (int a, b, c, d; i < n; i++) {
            long x = forceField[i][0], y = forceField[i][1], r = forceField[i][2];
            a = find(xs, (x << 1) - r, xz);
            b = find(xs, (x << 1) + r, xz);
            c = find(ys, (y << 1) - r, yz);
            d = find(ys, (y << 1) + r, yz);
            add(diff, a, c, b, d);
        }
        for (i = 1; i < diff.length; i++) {
            for (j = 1; j < diff[0].length; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                ans = Math.max(ans, diff[i][j]);
            }
        }

        return ans;
    }
    void add(int[][] diff, int a, int b, int c, int d) {
        diff[a][b]++;
        diff[c + 1][d + 1]++;
        diff[a][d + 1]--;
        diff[c + 1][b]--;
    }


    int find(long[] arr, long target, int n) {
        int l = 0, r = n - 1, mid = 0;
        while (l <= r) {
            mid = l + r >> 1;
            if (arr[mid] > target) {
                r = mid - 1;
            } else if (arr[mid] < target) {
                l = mid + 1;
            } else {
                return mid + 1;
            }
        }
        return -1;
    }
    int sort(long[] arr) {
        int n = arr.length, j = 0;
        Arrays.sort(arr);
        for (int i = 1; i < n; i++) {
            if (arr[i] != arr[j]) {
                arr[++j] = arr[i];
            }
        }
        return j + 1;
    }

}
